#pragma once

#include <boost/type_traits.hpp>
#include <boost/iterator.hpp>
#include <boostext/util/verify.hpp>




namespace boostext
{
	/**
	 * This class implements a doubly linked list that is highly optimized in order to conserve memory per instance.
	 * Instead of 28 bytes, this one only takes 4 bytes, but permits insertions at the end.
	 */
	template <typename T>
	class list
	{
	public:

		typedef T                                                 value_type;
		typedef typename boost::add_reference<value_type>::type   ref_type;
		typedef typename boost::add_const<value_type>::type       const_type;
		typedef typename boost::add_reference<const_type>::type   const_ref_type;

	private:

		/**
		 * This is the node class that actually stores the value_type as well
		 * as the previous & next information.
		 */
		class node
		{
		private:

			node*   m_prev;
			node*   m_next;
			T       m_value;

		public:

			/**
			 * Creates a node between the given previous and next node.
			 */
			node(const_ref_type value, node* prev, node* next)
				: m_prev(NULL)
				, m_next(NULL)
				, m_value(value)
			{
				connect(prev, next);
			}

			/**
			 * Destroys a node.
			 * Updates prev & next information of the previous and next nodes during
			 * destruction.
			 */
			~node()
			{
				disconnect();
			}



			/**
			 * Automatically converts this node into the value_type.
			 */
			operator const_ref_type() const
			{
				return m_value;
			}

			/**
			 * Automatically converts this node into the value_type.
			 */
			operator ref_type()
			{
				return m_value;
			}



			/**
			 * @return pointer to the next node
			 */
			node* next()
			{
				return m_next;
			}

			/**
			 * @return pointer to the next node
			 */
			const node* next() const
			{
				return m_next;
			}

			/**
			 * @return pointer to the previous node
			 */
			node* prev()
			{
				return m_prev;
			}

			/**
			 * @return pointer to the previous node
			 */
			const node* prev() const
			{
				return m_prev;
			}



			/**
			 * Connects this node between the previous and next node.
			 */
			void connect(node* prev, node* next)
			{
				m_prev = prev;
				m_next = next;

				if(prev)
					prev->m_next = this;
				if(next)
					next->m_prev = this;
			}

			/**
			 * Connects this node between the next and the next's previous node.
			 */
			void connect(node* next)
			{
				m_next = next;
				m_prev = next ? next->m_prev : NULL;

				if(m_prev != NULL)
					m_prev->m_next = this;
				if(m_next != NULL)
					m_next->m_prev = this;
			}

			/**
			 * Removes this node from the list, ie
			 * connects the previous and next node.
			 * This is done during destruction.
			 */
			void disconnect()
			{
				if(m_prev)
					m_prev->m_next = m_next;
				if(m_next)
					m_next->m_prev = m_prev;

				m_prev = NULL;
				m_next = NULL;
			}
		};
		///////////////////////////////////////////////////////////////////////////////////////////

	public:

		template <typename node_type, typename T>
		class basic_iterator
			: public boost::iterator_facade<basic_iterator<node_type, T>, T, boost::bidirectional_traversal_tag>
		{
		private:

			node_type*   m_current;

		public:

			basic_iterator()
				: m_current(NULL)
			{}

			basic_iterator(node_type* current)
				: m_current(current)
			{}



			/**
			 * Dereferences this iterator.
			 */
			reference dereference() const
			{
				return *m_current;
			}

			/**
			 * Advances this iterator to the next node.
			 */
			void increment()
			{
				verify(m_current != NULL);
				m_current = m_current->next();
			}

			/**
			 * Advances this iterator to the previous node.
			 */
			void decrement()
			{
				verify(m_current != NULL);
				m_current = m_current->prev();
			}

			/**
			 * Compares this iterator to another one.
			 */
			bool equal(const basic_iterator<node_type, T>& that) const
			{
				return m_current == that.m_current;
			}


			/**
			 * @return node this iterator points to
			 */
			node_type* node() const
			{
				return m_current;
			}
		};
		///////////////////////////////////////////////////////////////////////////////////////////

		typedef basic_iterator<node, value_type>         iterator;
		typedef basic_iterator<const node, const_type>   const_iterator;

	private:

		node*   m_first;

	public:

		/**
		 * Creates an empty list.
		 */
		list()
			: m_first(NULL)
		{}

		/**
		 * Creates a list with n copies of a value.
		 *
		 * @param value   the value to insert
		 * @param n       the number of copies to insert
		 */
		list(const_ref_type value, std::size_t n)
			: m_first(NULL)
		{
			for(std::size_t i = 0; i < n; ++i)
				insert(begin(), value);
		}

		/**
		 * Creates a list from a range of values.
		 *
		 * @param begin   iterator pointing to the first element of the range
		 * @param end     iterator pointing past the last element of the range
		 */
		template <typename Iter>
		list(Iter begin, Iter end)
			: m_first(NULL)
		{
			insert(this->begin(), begin, end);
		}

		/**
		 * Destroy this list.
		 */
		~list()
		{
			clear();
		}



		/**
		 * Calculates the size of this list.
		 * This function has a complexity of O(n).
		 *
		 * @return number of values in this list
		 */
		std::size_t size() const
		{
			std::size_t    n     = 0;
			const_iterator begin = this->begin();
			const_iterator end   = this->end();

			while(begin != end)
			{
				++n;
				++begin;
			}

			return n;
		}

		/**
		 * Tests if this list is empty or not.
		 * This function has a complexity of O(1)
		 */
		bool isEmpty() const
		{
			return m_first == NULL;
		}



		/**
		 * @return the first value in this list
		 * @throw programming_error when the list is empty
		 */
		ref_type first()
		{
			verify(m_first != NULL);
			return *m_first;
		}

		/**
		 * @return the first value in this list
		 * @throw programming_error when the list is empty
		 */
		const_ref_type first() const
		{
			verify(m_first != NULL);
			return *m_first;
		}



		/**
		 * Returns an iterator to the first element.
		 */
		iterator begin()
		{
			return iterator(m_first);
		}

		/**
		 * Returns an iterator to the first element.
		 */
		const_iterator begin() const
		{
			return const_iterator(m_first);
		}

		/**
		 * Returns an iterator past the last element.
		 */
		iterator end()
		{
			return iterator(NULL);
		}

		/**
		 * Returns an iterator past the last element.
		 */
		const_iterator end() const
		{
			return const_iterator(NULL);
		}



		/**
		 * Inserts the given element at the beginning of the list.
		 * This function has a complexity of O(1).
		 */
		void push_front(const_ref_type value)
		{
			insert(begin(), value);
		}

		/**
		 * Removes the element at the beginning of the list.
		 * This function has a complexity of O(1).
		 *
		 * @throws programming_error if the list is empty
		 */
		void pop_front()
		{
			erase(begin());
		}



		/**
		 * Inserts the given value before the given position.
		 * Elements cannot be inserted at the end.
		 * This function has a complexity of O(1).
		 *
		 * @param where   iterator before which the new value is inserted
		 */
		template <typename Iter>
		void insert(Iter where, const_ref_type value)
		{
			verify(isEmpty() || where != end());

			node* next = where.node();
			node* prev = isEmpty() ? NULL : next->prev();

			// We must have access to the actual node of that iterator
			// in order to insert a new node between that and it's previous
			// node.
			node* new_node = new node(value, prev, next);

			// In case the new element has been inserted at the beginning,
			// we must update our first pointer
			if(where == begin())
				m_first = new_node;
		}

		/**
		 * Inserts the given range of elements into this list.
		 * This function has a complexity of O(n), n being the number of values to insert.
		 *
		 * @param where   iterator before which the range will be inserted
		 * @param begin   iterator pointing to the first element of the range
		 * @param end     iterator pointing past the last element of the range
		 */
		template <typename Iter1, typename Iter2>
		void insert(Iter1 where, Iter2 begin, Iter2 end)
		{
			if(where == this->begin())
			{
				// in case the iterator points to the beginning of the
				// list, we must evaluate the begin iterator every time, otherwise
				// it could be mistaken as being the end
				while(begin != end)
				{
					insert(this->begin(), *begin);
					++begin;
				}
			}
			else
			{
				while(begin != end)
				{
					insert(where, *begin);
					++begin;
				}
			}
		}

		/**
		 * Erases the element at the given position.
		 * This function has a complexity of O(1).
		 *
		 * @return   iterator point to the next element, or end() if there is no next
		 * @throws   programming_error if the iterator points to the end of this list
		 * @warning   does not check if that iterator belongs to this list instance
		 */
		template <typename Iter>
		Iter erase(Iter where)
		{
			// end() should never be erased...
			verify(where != end());

			// We have to obtain a copy of the node that should be removed
			// but also the iterator to the next element, hence that code...
			Iter tmp = where++;

			// Update first
			if(tmp == begin())
				m_first = where.node();

			// The destructor of the node takes care of reconnecting pointers
			delete tmp.node();

			// Thanks to post-increment, where points to the next element
			return where;
		}

		/**
		 * Erases the given range of elements from this list.
		 * This function has a complexity of O(n), n being the number of values to erase.
		 */
		template <typename Iter>
		Iter erase(Iter begin, Iter end)
		{
			while(begin != end)
				begin = erase(begin);

			return begin;
		}

		/**
		 * Removes all values from this list.
		 */
		void clear()
		{
			iterator begin = this->begin();
			iterator end   = this->end();

			while(begin != end)
			{
				begin = erase(begin);
			}
		}

		/**
		 * Swaps this list with the other one.
		 * This function has a complexity of O(1).
		 */
		void swap(boostext::list<T>& that)
		{
			std::swap(m_first, that.m_first);
		}



		/**
		 * Searches for the first occurance of value in this list.
		 * This function has a complexity of O(n).
		 *
		 * @return iterator to the first occurance or to the end in case the value could not be found
		 */
		iterator find(const_ref_type value)
		{
			iterator begin = this->begin();
			iterator end   = this->end();

			while(begin != end)
			{
				if(*begin == value)
					break;

				++begin;
			}

			return begin;
		}

		/**
		 * Searches for the first occurance of value in this list.
		 * This function has a complexity of O(n).
		 *
		 * @return iterator to the first occurance or to the end in case the value could not be found
		 */
		const_iterator find(const_ref_type value) const
		{
			const_iterator begin = this->begin();
			const_iterator end   = this->end();

			while(begin != end)
			{
				if(*begin == value)
					break;

				++begin;
			}

			return begin;
		}
	};
	///////////////////////////////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////////////////////////////
